package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 61. 旋转链表 中档题
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * <p>
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * <p>
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 * @author zjj_admin
 * @date 2022/11/3 13:40
 */
public class RotateList {

    public static void main(String[] args) {

    }


    /**
     * 思路
     * 给定一个头结点，dump ，dummy.next = head
     * 计算出链表的长度 length
     * 假设链表为 2 3 4 5 6 ，则length = 5;
     * 取 m = k % length
     * 让 dummy.next 执行第 m 个节点即可
     * 当 m = 0;时，直接返回即可
     * 当 m 不等于0时，重新定位头结点和尾节点即可
     * 头结点为 length - now，尾节点为 length -now -1
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curr;
        curr = head;
        int length = 0;
        while (true) {
            if (curr == null) {
                break;
            }
            length++;
            curr = curr.next;
        }
        int now = k % length;
        if (now == 0) {
            return head;
        }
        curr = head;
        ListNode newTail = new ListNode(-1);
        ListNode dummy = new ListNode(-1);
        for (int i = 0; i < length; i++) {
            //找到新的尾节点
            if (i == (length - now - 1)) {
                newTail = curr;
            }
            //找到新的头结点
            if (i == length - now) {
                dummy.next = curr;
            }
            curr = curr.next;
            if (curr.next == null) {
                curr.next = head;
                newTail.next = null;
            }
        }
        return dummy.next;
    }
}
